home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / DDJMAG / DDJ8609.ZIP / IVOR.SEP < prev    next >
Text File  |  1986-09-30  |  5KB  |  171 lines
  1. /* Listing one */
  2. /*Radix sort listing*/
  3.  
  4. /* These includes are necessary to get the proper declarations for some of
  5.    the Macintosh routines */
  6. #include event.h
  7. #include quickdraw.h
  8.  
  9. typedef struct {        /*Define a structure for the sort keys*/
  10.     struct sortrec *ptr;    /*Pointer to next key*/
  11.     char sortdat[KEYSIZ];    /*The key, containing KEYSIZ bytes*/
  12.     } sortrec;
  13. char *lmalloc();
  14.  
  15. main()
  16.  
  17. {    sortrec *begin,*first,*start,*temp;
  18.     int i,j,recno;
  19.     long tick;
  20.     unsigned char dat;
  21.     MaxApplZone();            /*Get maximum size application heap*/
  22.     begin = (sortrec *) lmalloc(0x40000); /*Allocate 256K for sortrecs*/
  23.         /*Check if allocation was successful and exit if not*/
  24.         if (!begin) {
  25.         printf("\nNot enough memory in heap");
  26.         _exit();
  27.         }
  28.     first = begin;            /*Point to first record*/
  29.     printf("How many recs to sort\n");
  30.     scanf ("%d",&recno);
  31.     for (i=0; i<recno; ++i) {
  32.         first->ptr = first+1;    /*Set pointer to next record in heap*/
  33.         for (j=0; j< KEYSIZ; ++j)    /*Fill with KEYSIZ random bytes*/
  34.             first->sortdat[j] = (Random()&0x7fff)%256;
  35.         ++first;        /*Point to next sort key record*/
  36.         }            /*All records allocated and filled*/
  37.     first->ptr = 0;            /*Terminate the linked list*/
  38.     tick = TickCount();        /*Get the current time*/
  39.     start = sort(KEYSIZ,begin);    /*Sort the list*/
  40.     printf("\nTickcount=%ld",TickCount()-tick); /*Print elapsed time*/
  41.     }
  42.     
  43. sortrec *sort(a,b)
  44. int a;        /*number of bytes in the sort key*/
  45. sortrec *b;    /*Pointer to head of linked list to be sorted*/
  46.  
  47. {    /*First and last are pointers to follow two linked lists whose
  48.       heads are start and start2.  Temp follows the full-length
  49.       original or partly sorted list*/
  50. sortrec *first,*last,*start,*temp,*start2;
  51.     static char mask[8] = { 1,2,4,8,16,32,64,128};/*Individual bit masks*/
  52.     register i,j;
  53.  
  54.     start = b;            /*point to original unsorted list*/
  55.     for (i = a-1; i >= 0; --i) { /*Loop for all bytes of the sort key*/
  56.         for (j = 0; j < 8; ++j) { /*Loop for all bits of each byte*/
  57.             first = last = start2 = 0;  /*Set up working ptrs*/
  58.             /*Loop for each key in the list*/
  59.             for (temp = start; temp; temp = temp->ptr) {
  60.                 if (temp->sortdat[i]&mask[j])
  61.     /*Value of the bit was 1.  If last list is empty, initialize it*/
  62.                     if (last==0) start2 = temp;
  63.                     /*else add this item to the list*/
  64.                     else last->ptr = temp; 
  65.                     last = temp;
  66.                     }
  67.     /*Value was 0. If first list empty, initialize it*/
  68.                 else { 
  69.                     if (first==0) start = temp;
  70.                     /*else add this item to the list*/
  71.                     else first->ptr = temp;
  72.                     first = temp;
  73.                     }
  74.                 } /*End of list*/
  75.             /*If last list not empty, terminate it*/
  76.             if (last) last->ptr = 0;
  77.             /*if first list empty, use last only*/
  78.             if (first == 0)start = start2;
  79.             /*Else add last list to first list*/
  80.             else first->ptr = start2; 
  81.             } /*All bits this byte examined*/
  82.         } /*all bytes examined*/
  83.     return start;
  84.     }
  85.  
  86.  
  87.  
  88.  
  89.  
  90. /* Listing two */
  91. /*Shell sort listing*/
  92.  
  93. /*Includes for certain Macintosh routines*/
  94. #include quickdraw.h
  95. #include event.h
  96. typedef struct {    /*This structure consists only of KEYSIZ bytes*/
  97.     char sortdat[KEYSIZ];
  98.     } sortrec;
  99. char *lmalloc();
  100.  
  101. main()
  102.  
  103. {    int i,j,recno;
  104.     long tick;
  105.     sortrec *array, *base;
  106.     unsigned char dat;
  107.     MaxApplZone();    /*Get heap space, allocate 256K for sort keys*/
  108.     array = base = (sortrec *) lmalloc(0x40000);
  109.     printf("How many recs to sort\n");
  110.     scanf ("%d",&recno);
  111.     if (!array) {
  112.         printf("\nNot enough memory in heap");
  113.         exit();
  114.         }
  115. /*Fill the area with random data.  Use array as a pointer to all records*/    
  116.     for (i=0; i<recno; ++i) { 
  117.         for (j=0;j<KEYSIZ;++j) {
  118.             dat = (Random()&0x7fff)%256;
  119.             array->sortdat[j] = dat;
  120.             }
  121.         ++array;
  122.         }
  123.     tick = TickCount();        /*Get the current time*/
  124.     sort(KEYSIZ,base,comp,swap,recno);
  125.     printf("\nTickcount=%ld",TickCount()-tick);    /*Print elapsed time*/
  126.     }
  127.  
  128. sortrec *sort(size,start,comp,swap,n)
  129. int size,n;
  130. sortrec *start;
  131. long (*comp)(),(*swap)();
  132.  
  133. /*This is essentially identical to that in the  Kernighan and Ritchie text.
  134.   The call includes size (the number of records), start (a pointer to the
  135.   first record), comp and swap (routines for comparing and swapping byte
  136.   strings, given pointers to them, and the number of bytes contained therein,
  137.   and n (the number of bytes in the sort key)*/
  138.  
  139. {    int gap,i,j;
  140.     for (gap = n/2; gap > 0; gap /= 2)
  141.         for (i=gap; i<n; i++)
  142.             for (j=i-gap; j>=0; j-=gap) {
  143.                 if ((*comp)(start+j,start+j+gap,size) <= 0) break;
  144.                 (*swap)(start+j,start+j+gap,size);
  145.                 }
  146.     }
  147.  
  148. comp(val1,val2,n)
  149. char *val1,*val2;
  150. int n;
  151.  
  152. {    register i;
  153.     for (i=0; i<n; ++i) {
  154.         if (*(val1+i) < *(val2+i)) return (-1);
  155.         else if (*(val1+i) > *(val2+i)) return(1);
  156.         }
  157.     return 0;
  158.     }
  159.  
  160. swap(val1,val2,n)
  161. char *val1,*val2;
  162. int n;
  163.  
  164. {    register i,temp;
  165.     for (i=0; i<n; ++i) {
  166.         temp = *val1;
  167.         *val1++ = *val2;
  168.         *val2++ = temp;
  169.         }
  170.     }
  171.